<!doctype html><html lang=cn-zh><head><meta charset=UTF-8><meta name=viewport content="width=device-width,initial-scale=1"><meta http-equiv=X-UA-Compatible content="IE=edge"><style type=text/css>body{font-family:monospace}</style><title>[算法笔记]侏儒排序算法实现和复杂度分析</title>
<meta name=description content="A blog maintained by Vimiix."><link rel=stylesheet href=/css/style.css><script>var _hmt=_hmt||[];(function(){var e,t=document.createElement("script");t.src="https://hm.baidu.com/hm.js?7c24231917964240bae97e813810620c",e=document.getElementsByTagName("script")[0],e.parentNode.insertBefore(t,e)})()</script></head><body><header>====================<br>== Hi, I'm Vimiix ==<br>====================<div style=float:right;color:gray;font-size:x-large>Get hands dirty.</div><br><p><nav><a href=https://www.vimiix.com/><b>首页</b></a>.
<a href=/posts/><b>文章列表</b></a>.
<a href=/projects/><b>开源项目</b></a>.
<a href=/tags/><b>标签</b></a>.
<a href=/friends/><b>友链</b></a>.
<a href=/about/><b>关于我</b></a>.
<a href=/index.xml><b>RSS</b></a>.</nav></p></header><main><article><h1>[算法笔记]侏儒排序算法实现和复杂度分析</h1><b><time>2017.07.31 15:58</time></b>
<a href=/tags/algorithms>algorithms</a>
<a href=/tags/python>Python</a><div><h1 id=侏儒排序>侏儒排序</h1><h3 id=介绍>介绍</h3><p>侏儒排序是由 Hamid Sarbazi-Azad 在 2000 年提出的，也叫愚人排序法（Stupid sort）。这种排序算法一种简单的复杂度为<code>平方级</code>的排序算法，一般实际生产中不会用到。</p><h3 id=python-代码>Python 代码</h3><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-Python data-lang=Python><span style=display:flex><span>	<span style=color:#66d9ef>def</span> <span style=color:#a6e22e>gnomesort</span>(seq):
</span></span><span style=display:flex><span>	  i <span style=color:#f92672>=</span> <span style=color:#ae81ff>0</span>
</span></span><span style=display:flex><span>	  <span style=color:#66d9ef>while</span> i <span style=color:#f92672>&lt;</span> len(seq):
</span></span><span style=display:flex><span>	    <span style=color:#66d9ef>if</span> i<span style=color:#f92672>==</span><span style=color:#ae81ff>0</span> <span style=color:#f92672>or</span> seq[i<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>]<span style=color:#f92672>&lt;=</span>seq[i]:
</span></span><span style=display:flex><span>	      i <span style=color:#f92672>+=</span> <span style=color:#ae81ff>1</span>
</span></span><span style=display:flex><span>	    <span style=color:#66d9ef>else</span>:
</span></span><span style=display:flex><span>	      seq[i], seq[i<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>] <span style=color:#f92672>=</span> seq[i<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>], seq[i]
</span></span><span style=display:flex><span>	      i <span style=color:#f92672>-=</span> <span style=color:#ae81ff>1</span>
</span></span><span style=display:flex><span>	  <span style=color:#66d9ef>return</span> seq
</span></span></code></pre></div><h3 id=说明>说明</h3><p>侏儒排序法中只有一个简单的 while 循环和额一个索引范围为<code>0</code>到<code>len(seq)-1</code>的索引变量。这和容易让人以为它是一个线性时间的算法，但这个结论被最后一行中的<code>i -= 1</code>语句给否定了。要想搞清楚该算法究竟运行了多长时间，我们必须搞懂他工作过程中的一些细节。</p><p>起初，我们会从左边开始扫描（持续递增 i），直到找到一个<code>seq[i-1]</code>大于<code>seq[i]</code>的位置 i,这时两个值顺序就错了，于是<code>else</code>部分开始生效。</p><p>else 分支会持续交换<code>seq[i]</code>与<code>seq[i-1]</code>的值并递减 i，直到其再次恢复到之前<code>seq[i-1] &lt;= seq[i]</code>的顺序。换句话说，该算法会沿着目标序列交叉向上扫描来发现错了位的元素，并将其经过反复交换下移到合适的位置。那么其整体开销是多少呢？先忽略到平均情况，只关注最好和最坏的情况。</p><p>最好的情况当然是目标序列已经排好序，这时 gnomesort 只需要将整个序列扫描一遍即可便停止，其运行时间为 Ω(n)。</p><p>而最坏的情况就没有那么简单了，但也没有多复杂。需要注意的是，通常每当我们发现一个元素错位时，这之前的所有元素都应该是已经排好序了。所以，当我们将新元素移动到合适的位置的时候是不会发生冲突的。也就是说，每纠正一个错位元素，已排序元素的数量就会有所增加，并且下一个错位的元素会出现在更后面的位置上，所以可能的最坏的情况就是查找并移动这些错位的元素的开销与其位置形成了正比关系。因而最糟糕的运行时间就应该是<code>1+2+3+...+(n-1)</code>，也就是 O(n^2)</p><p>所以，Ω(n)和 O(n^2)就表示了侏儒算法的最好和最坏情况的上下严格边界。</p></div></article></main><aside><div><div><h3>LATEST POSTS</h3></div><div><ul><li><a href=/posts/2025-10-16-kubernetes-apiserver-authorization-mechanism/>Kubernetes APIServer 鉴权机制</a></li><li><a href=/posts/2025-09-30-kubernetes-apiserver-authentication-mechanism/>Kubernetes APIServer 认证机制</a></li><li><a href=/posts/2024-12-16-deploy-kubernetes-by-kubeadm/>使用 kubeadm 搭建 kubernetes 集群</a></li><li><a href=/posts/2024-09-20-how-to-code-review/>如何做code review</a></li><li><a href=/posts/2024-08-12-weakref-in-python/>Python中的弱引用</a></li></ul></div></div></aside><footer><p>Social Links:
<a href=https://github.com/vimiix><b>Github</b></a>.
<a href=https://www.douban.com/people/vimiix/><b>Douban</b></a>.
<a href=mailto:i@vimiix.com><b>Email</b></a>.<br><hr>&copy; 2017-2025
Vimiix Yao; All rights reserved.
<a href=https://beian.miit.gov.cn/>京ICP备19015214号-1</a></p><script src=https://l2dwidget.js.org/lib/L2Dwidget.min.js></script><script>L2Dwidget.init({model:{jsonPath:"https://unpkg.com/live2d-widget-model-tororo@1.0.5/assets/tororo.model.json"}})</script></footer></body></html>